'''
给定一个正整数 n, 判断 n 是否是一个质数
一个数字，除了 1 和它本身，没有其它因数
2...n - 1
'''
def is_prime(n):
    for i in range(2, n):
        if n % i == 0: # n 能被 i 整除
            return False # n 不是质数
    
    return True

'''
因数分解：把一个整数 n，分解成几个质数的乘积。
18 = 2 x 3 x 3

18 / 2 = 9
9 / 2 = X
9 / 3 = 3

3 / 3 = 1
对 n 进行因数分解，如果 n 是质数，就直接打印它本身，如果是合数，就打印因数分解的结果。
factorization(18) => 2 x 3 x 3
factorization(5) => 5
'''
def factorization(n):
    if is_prime(n):
        print(n)
        return
    
    # 如果 n 不是质数，这个合数它必然能被 2 整除，或者被 3 整除
    i = 2
    result = "" # 计算表达式

    # 对 n 因数分解，不断对 n 进行因数分解，直到 n 等于 1 为止
    # 只要被分解的数字不等于 1，就一直分解
    while n != 1:
        # 对 n 因数分解

        if n % i == 0:
            # n 能被 i 整除
            # ...
            # 数字 i 是 n 的一个因数，i 肯定会出现在 n 的因数分解表达式里。
            # 当我们最后一次分解 n 的时候，我们不能在 result 上拼接 ' x'
            # 如何知道是最后一次分解？
            # n // i == 1 就是最后一次分解了
            if n // i == 1:
                # 最后一次分解
                result += f'{i}'
            else:
                result += f'{i} x ' # String interpolation
            n = n // i
            i = 2
        else:
            # n 不能被 i 整除, i 加 1，我们要尝试下一个除数
            i += 1

    print(result)

factorization(18)

'''
对 18 进行因数分解 = 2 x 对 9 的因数分解的结果
或者
3 x ...
'''
def solve(n):
    if is_prime(n):
        return f"{n}"
    
    # 当 n 不是质数的时候，对 n 进行因数分解，只有两种情况
    # 2 x ...
    # 3 x ...
    if n % 2 == 0:
        # 2 x ...
        expr = solve(n // 2)
        return f"2 x {expr}"
    else:
        # n 不能被 2 整除，n 必然能被 3 整除
        # 3 x ...
        expr = solve(n // 3)
        return f"3 x {expr}"

print(solve(18))